#include <iostream>

using namespace std;


class Backpack 
{
public:
    inline int bp01_simple() {
        for (int i = 0; i < n_; i++) {
            for (int j = 0; j <= w_; j++) {
                if (j < w[i]) {
                    dp[i+1][j] = dp[i][j];
                } else {
                    dp[i+1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
                }       
            }
        }
        return dp[n_][w_];
    }

    inline int bp01_complex() {
        for (int i = 0; i < n_; i++) {
            for (int j = 0; j <= n_ * v_; j++) {
                if (j < v[i]) {
                    dp[i + 1][j] = dp[i][j];
                } else {
                    dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i]);
                }
            }
        }
        int res = 0;
        for (int i = 0; i <= n_ * v_; i++) {
            if (dp[n_][i] <= w_) {
                res = i;
            }
        }
        return res;
    }

    inline int bp_complete() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= w_; j++) {
                if (j < w[i]) {
                    dp[i + 1][j] = dp[i][j];
                } else {
                    dp[i + 1][j] = max(dp[i][j], dp[i+1][j - w[i]] + v[i]);
                }
            }
        }
        return dp[n_][w_];
    }
private:
    int n_;
    int w_;
    int w[];
    int v[];
    int dp[][];
};

int main(int argc, char** argv)
{
    //stuff
    return 0;
}
